﻿// 0906train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
赤道上均匀部署了N个转向发动机（环状）
1. 初始状态下所有的发动机都是未启动状态；
2. 发动机启动的方式分为“手动启动”和“关联启动”两种方式；
3. 如果在时刻1一个发动机被启动，下一个时刻2与之相邻的两个发动机就会被“关联启动”；
4. 如果准备启动某个发动机时，它已经被启动了，则什么都不用做；
5. 发动机0与发动机N-1是相邻；（环状）
地球联合政府准备挑选某些发动机在某些时刻进行“手动启动”，当然最终所有的发动机都会被启动。
哪些发动机最晚被启动呢

输入描述
第一行两个数字N和E，中间有空格
N代表部署发动机的总个数，E代表计划手动启动的发动机总个数1<N<=1000，1<=E<=1000，E<=N
接下来共E行,每行都是两个数字T和P，中间有空格
T代表发动机的手动启动时刻，P代表此发动机的位置编号

输出描述
第一行一个数字N，以回车结束N代表最后被启动的发动机个数
第二行N个数字，中间有空格，以回车结束每个数字代表发动机的位置编号，从小到大排序

输入
8 2
0 2
0 6
输出
2
0 4

0 1 2 3 4 5 6 7
 */

/*
 1先把num_vec中的数，推到start_map中
 2把0时刻的数字推进去，
 3if(start_map.count(time)>0，那么把start_map中的数组推进去
 4启动的推进去track里面，加个start_count, start_count==total结束
 */
class Solution01
{
public:
	unordered_map<int, vector<int>>start_map;
	deque<int>bfs_queue;
	vector<vector<int>>track_vec; //记录每个时刻出发的

	void updateQueue(int top_node, vector<bool>&checked, int total)
	{
		int next_node;
		if (top_node != total - 1)
		{
			next_node = top_node + 1;
		}
		else
		{
			//环状
			next_node = 0;
		}

		int prev_node;
		if (top_node != 0)
		{
			prev_node = top_node - 1;
		}
		else
		{
			//环状
			prev_node = total - 1;
		}

		vector<int>checked_node_v = { prev_node, next_node };
		for (auto&node: checked_node_v)
		{
			bool is_visited = checked[node];
			if (!is_visited)
			{
				//入队，标记已访问
				checked[node] = true;
				//更新checked
				track_vec[search_count_].push_back(node);
				bfs_queue.push_back(node);
			}
		}
		//updateQueue
	}

	Solution01(int total, vector<vector<int>>&num_vec)
	{
		//标记每一台是否被启动，编号从0开始
		vector<bool>checked(total, false);

		
		//记录手动启动的，时刻:{编号}
		for (auto&status_v:num_vec)
		{
			int i_start_time = status_v[0], index = status_v[1];
			start_map[i_start_time].push_back(index);
			//记录最早出发时间
			start_time_ = min(start_time_, i_start_time);
		}
		curr_time_ = start_time_ - 1;

		//start_map[0] 0时刻出发的最先入队
		for (auto&first_index:start_map[start_time_])
		{
			//0时刻出发，最先入队，入队就是被启动的
			checked[first_index] = true;
			bfs_queue.push_back(first_index);
		}
		track_vec.push_back(start_map[start_time_]);


		while (!bfs_queue.empty())
		{
			search_count_ += 1; //起始为0，记录下一层层数
			curr_time_ += 1; //第一次进来，加完curr_time_==start_time_

			if (curr_time_ > start_time_ && start_map.count(curr_time_)>0)
			{
				//说明下个时刻有被启动的，入队
				for (auto&i_index:start_map.at(curr_time_))
				{
					//标记已访问
					checked[i_index] = true;
					bfs_queue.push_back(i_index);
				}
			}

			//记录下一时刻点亮的机器
			vector<int>empty_v;
			track_vec.push_back(empty_v);

			int q_size = bfs_queue.size();
			for (int i=0; i<q_size; i++)
			{
				int top_node = bfs_queue.front();
				bfs_queue.pop_front();

				//updateQueue(int top_node, vector<bool>&checked, int total)
				updateQueue(top_node, checked, total);

				//for (int i=0; i<q_size; i++)
			}

			//while (!bfs_queue.empty())
		}
		track_vec.pop_back();

		//退出队列的时候，就是最后一层
		int back_size = track_vec.back().size();
		cout << back_size << endl;

		vector<int>result = track_vec.back();
		sort(result.begin(), result.end());

		for (int i=0; i< back_size; i++)
		{
			cout << result[i];
			if (i!=back_size-1)
			{
				cout << ' ';
			}
		}

		//Solution01
	}
private:
	int search_count_ = 0; //track当前层数
	int start_time_ = INT_MAX;
	int curr_time_ = -1;
};


/*
 二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，
 对于存储在下标 N 的节点，它的左子节点和右子节点分存储在下标 2*N 和 2*N+1，
 并且我们用值 -1 代表一个节点为空。
给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。

输入描述
输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。
注意第一个元素即为根节点的值，即数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略了。
输入的树最多为7层。

输出描述
输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个。

输入
3 5 7 -1 -1 2 4
输出
3 7 2
 */
class Solution02
{
public:
	struct TreeNode
	{
		TreeNode* left = nullptr;
		TreeNode* right = nullptr;
		int val;
		TreeNode() = default;
		TreeNode(int val, TreeNode* left, TreeNode* right):val(val), left(left), right(right) {};
	};

	TreeNode* buildTree(vector<int>&num_vec, int index)
	{
		int node_val = num_vec[index];

		TreeNode* left = nullptr;
		if (2*index+1<num_vec.size() && num_vec[2 * index + 1]!=-1)
		{
			left = buildTree(num_vec, 2 * index + 1);
		}

		TreeNode* right = nullptr;
		if (2*index+2<num_vec.size() && num_vec[2 * index + 2] != -1)
		{
			right = buildTree(num_vec, 2 * index + 2);
		}
		return new TreeNode(node_val, left, right);
	}

	Solution02(vector<int>&num_vec)
	{
		TreeNode* root = buildTree(num_vec, 0);

		deque<TreeNode*>bfs_queue;
		bfs_queue.push_back(root);

		vector<int>root_vec = { root->val };
		path_queue.push_back(root_vec);

		vector<int>result;
		int min_val = INT_MAX;
		while (!bfs_queue.empty())
		{
			int q_size = bfs_queue.size();

			for (int i=0; i<q_size; i++)
			{
				TreeNode* top_node = bfs_queue.front();
				bfs_queue.pop_front();
				vector<int>top_path = path_queue.front();
				path_queue.pop_front();

				if (top_node->left==nullptr && top_node->right==nullptr)
				{
					if (top_node->val < min_val)
					{
						//最小叶子节点
						result = top_path;
						min_val = top_node->val;
					}
				}

				if (top_node->left!=nullptr)
				{
					bfs_queue.push_back(top_node->left);

					vector<int>left_path = top_path;
					left_path.push_back(top_node->left->val);
					path_queue.push_back(left_path);
				}

				if (top_node->right!=nullptr)
				{
					bfs_queue.push_back(top_node->right);

					vector<int>right_path = top_path;
					right_path.push_back(top_node->right->val);
					path_queue.push_back(right_path);
				}

			}
			//while (!bfs_queue.empty())
		}

		for (int i=0; i<result.size(); i++)
		{
			cout << result[i];
			if (i!=result.size()-1)
			{
				cout << ' ';
			}
		}

		//Solution02
	}
private:
	deque<vector<int>>path_queue;
};


int main()
{
	{
		//3 5 7 -1 -1 2 4
		vector<int>num_vec;
		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		string token;
		while (oh_sstream>>token)
		{
			num_vec.push_back(stoi(token));
		}

		Solution02 solu(num_vec);

		return 0;
	}
/*
8 2
0 1
1 7
输出
2
4 5
*/
	int total, v_size;
	cin >> total >> v_size;
	cin.ignore();

	vector<vector<int>>num_vec;
	for (int i=0; i<v_size; i++)
	{
		vector<int>min_vec;
		string input;
		getline(cin, input);
		stringstream oh_sstream(input);
		string token;
		while (oh_sstream>>token)
		{
			min_vec.push_back(stoi(token));
		}
		num_vec.push_back(min_vec);
	}
	//Solution01(int total, vector<vector<int>>&num_vec)
	Solution01 solu(total, num_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
